﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _02_LinkedList
{
   class MyLinkedList
   {
      // 数据项
      public int val { get; set; }
      public MyLinkedList next { get; set; }

      public MyLinkedList(int val)
      {
         this.val = val;
         this.next = null;
      }

      public MyLinkedList(IEnumerable<int> ie)
      {
         var iter = ie.GetEnumerator();
         MyLinkedList cur;
         while (iter.MoveNext())
         {
            cur = new MyLinkedList(iter.Current);
            cur.next = this.next;
            this.next = cur;
         }
         iter.Reset();
      }

      // 生成随机链表
      public static MyLinkedList GenerateRandList(int count)
      {
         MyLinkedList dummyHead = new MyLinkedList(0);
         MyLinkedList curNode;

         for (int i = 0; i < count; i++)
         {
            curNode = new MyLinkedList(new Random().Next(0, 101));
            curNode.next = dummyHead.next;
            dummyHead.next = curNode;
         }

         return dummyHead.next;
      }

      // 遍历链表
      public void Traverse(Action<int> action)
      {
         MyLinkedList cur = this;
         if (cur == null) return;
         while (cur != null)
         {
            action.Invoke(cur.val);
            cur = cur.next;
         }
      }

      // 打印函数
      public void PrintLinkedList()
      {
         Traverse(val =>
         {
            Console.Write($"{val} ");
         });
      }

      // 翻转链表
      public MyLinkedList ReverseLinkedList()
      {
         MyLinkedList p1 = this, p2 = this.next, p3 = null;
         p1.next = null;
         while (p2 != null)
         {
            p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
         }
         return p1;
      }

      // 拷贝链表
      public MyLinkedList CopyLinkedList()
      {
         MyLinkedList p = this, q, head;

         q = new MyLinkedList(p.val);
         head = q;
         p = p.next;

         while (p != null)
         {
            q.next = new MyLinkedList(p.val);
            p = p.next;
            q = q.next;
         }

         return head;
      }

      // 打印两个有序链表的公共部分
      public static void PrintSamePart(MyLinkedList l1, MyLinkedList l2)
      {
         MyLinkedList p = l1, q = l2;
         while (p != null && q != null)
         {
            if (p.val == q.val)
            {
               Console.Write(p.val + " ");
               p = p.next;
               q = q.next;
            }
            else if (p.val < q.val)
               p = p.next;
            else
               q = q.next;
         }
      }

      // 判断回文链表 --- 辅助栈
      public static bool IsPalindrome_1(MyLinkedList list)
      {
         MyLinkedList fast = list, slow = list;
         while (fast != null && fast.next != null)
         {
            fast = fast.next.next;
            slow = slow.next;
         }

         // 借助栈存放逆序结构
         Stack<int> stack = new Stack<int>();
         while (slow != null)
         {
            stack.Push(slow.val);
            slow = slow.next;
         }

         slow = list;
         while (stack.Count != 0)
         {
            if (slow.val != stack.Pop())
               return false;
            slow = slow.next;
         }

         return true;
      }

      // 判断回文链表 --- 快慢指针
      public static bool IsPalindrome_2(MyLinkedList list)
      {
         if (list == null)
            return false;
         else if (list.next == null)
            return true;
         MyLinkedList fast = list, slow = list;
         while (fast != null && fast.next != null)
         {
            fast = fast.next.next;
            slow = slow.next;
         }

         // 翻转后面的链表
         MyLinkedList rightHead = slow, p1 = slow, p2 = slow.next, p3;
         p1.next = null;
         while (p2 != null)
         {
            p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
         }

         // 比较判断
         p2 = p1;
         fast = list;
         bool res = true;
         while (p1 != null)
         {
            if (fast.val != p1.val)
            {
               res = false;
               break;
            }
            fast = fast.next;
            p1 = p1.next;
         }

         // 复原
         p1 = p2;
         p2 = p1.next;
         p1.next = null;
         while (p2 != null)
         {
            p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
         }

         return res;
      }

      private static void Swap(List<MyLinkedList> list, int aI, int bI)
      {
         MyLinkedList temp = list[aI];
         list[aI] = list[bI];
         list[bI] = temp;
      }

      // partition链表 --- 借助数组
      public static MyLinkedList Partition_1(MyLinkedList list, int pivot)
      {
         // list -> arr
         List<MyLinkedList> help = new List<MyLinkedList>();
         MyLinkedList p = list;
         while (p != null)
         {
            help.Add(p);
            p = p.next;
         }

         // arr partition
         int sr = -1, br = help.Count, i = 0;
         while (i < br)
         {
            if (help[i].val < pivot)
               Swap(help, i++, sr++ + 1);
            else if (help[i].val == pivot)
               i++;
            else
               Swap(help, i, br-- - 1);
         }

         // arr -> list
         MyLinkedList dummyHead = new MyLinkedList(0), tail = dummyHead;
         for (int j = 0; j < help.Count; j++, tail = tail.next)
         {
            MyLinkedList cur = new MyLinkedList(help[j].val);
            cur.next = tail.next;
            tail.next = cur;
         }

         return dummyHead.next;
      }

      // partition链表 --- 六变量法
      public static MyLinkedList Partition_2(MyLinkedList list, int pivot)
      {
         MyLinkedList sh = null, st = null,
            eh = null, et = null,
            bh = null, bt = null;

         MyLinkedList p = list;
         for (; p != null; p = p.next)
         {
            // 小于区
            if (p.val < pivot)
            {
               if (sh == null)
               {
                  sh = p;
                  st = p;
               }
               else
               {
                  st.next = p;
                  st = p;
               }
            }
            // 等于区
            else if (p.val == pivot)
            {
               if (eh == null)
               {
                  eh = p;
                  et = p;
               }
               else
               {
                  et.next = p;
                  et = p;
               }
            }
            // 大于区
            else
            {
               if (bh == null)
               {
                  bh = p;
                  bt = p;
               }
               else
               {
                  bt.next = p;
                  bt = p;
               }
            }
         }

         // 六指针串起
         if (sh != null) // 有小于区
         {
            st.next = eh;  // 小于尾 连 等于头
            et ??= st;  // 谁有值 谁就要连大于头
         }
         if (et != null)   // 有等于尾
            et.next = bh;  // 等于尾 连 大于头
         if (bt != null)
            bt.next = null;
         return sh ?? eh ?? sh; // 哪个头有值 返回哪个头
      }

      // 判断链表是否有环
      public MyLinkedList GetCircle()
      {
         MyLinkedList fast = this, slow = this;
         if (fast == null || fast.next == null || fast.next.next == null)
            return null;

         fast = fast.next.next;
         slow = slow.next;
         while (fast != slow)
         {
            if (fast.next == null || fast.next.next == null)
               return null;
            fast = fast.next.next;
            slow = slow.next;
         }

         slow = this;
         while (fast != slow)
         {
            fast = fast.next;
            slow = slow.next;
         }

         return fast;
      }

      // 判断链表是否相交 --- 借助哈希表
      public static bool IsCross_1(MyLinkedList l1, MyLinkedList l2)
      {
         // 记录链表1信息
         HashSet<MyLinkedList> record = new HashSet<MyLinkedList>();
         MyLinkedList p = l1;
         while (p != null)
         {
            record.Add(p);
            p = p.next;
         }

         // 根据哈希表考察链表2
         p = l2;
         while (p != null)
         {
            if (record.Contains(p))
               return true;
            p = p.next;
         }

         return false;
      }

      // 获得链表长度
      private int GetLength(out MyLinkedList end)
      {
         int len = 0;
         MyLinkedList p = this;
         while (p.next != null)
         {
            len++;
            p = p.next;
         }
         end = p;
         return len + 1;
      }
      private int GetLength(MyLinkedList endPos)
      {
         int len = 0;
         MyLinkedList p = this;
         while (p != endPos)
         {
            len++;
            p = p.next;
         }
         return len;
      }

      // Y结构
      private static MyLinkedList YResult(MyLinkedList l1, MyLinkedList l2, int len1, int len2)
      {
         MyLinkedList i = (len1 < len2) ? l1 : l2,    // i = 短的
            j = (i == l1) ? l2 : l1;   // j = 长的
         int delta = Math.Abs(len1 - len2);
         for (int count = 0; count < delta; count++, i = i.next)  // 短的先移动
            ;
         for (; i != j; i = i.next, j = j.next) // 两个链表移动至相遇
            ;
         return i;
      }

      // 判断链表是否相交 --- 快慢指针
      public static MyLinkedList IsCross_2(MyLinkedList l1, MyLinkedList l2)
      {
         // 获取链表的环情况
         MyLinkedList loop1 = l1.GetCircle();
         MyLinkedList loop2 = l2.GetCircle();

         // 均无环
         if (loop1 == null && loop2 == null)
         {
            MyLinkedList end1, end2;
            int len1 = l1.GetLength(out end1),
               len2 = l2.GetLength(out end2);
            // 平行结构
            if (end1 != end2)
               return null;

            // Y结构
            return YResult(l1, l2, len1, len2);
         }
         // 均有环
         else if (loop1 != null && loop2 != null)
         {
            // 蜗牛结构
            if (loop1 == loop2)
            {
               int len1 = l1.GetLength(loop1),
                  len2 = l2.GetLength(loop2);
               return YResult(l1, l2, len1, len2);
            }
            else
            {
               while (loop1.next != loop1)
               {
                  // 环岛结构
                  if (loop1 == loop2)
                     return loop1;
                  loop1 = loop1.next;
               }
               // 66结构
               return null;
            }
         }
         // 一个有环，一个无环
         else
         {
            return null;
         }
      }
   }
}
